Some of public key encryptions are configured by use of a subset of a finite field (a set of numbers; the four arithmetic operations are possible by only the elements in the set). Assuming that the number of elements in the subset is A and the number of elements in the finite field is B, A≦B is given. For example, A=2^160 and B=2^1024 are used for the public key encryptions. Generally, the number of bits required for expressing X elements is log—2X bits. However, although only A elements in the subset are used for the existing public key encryptions, some encryption systems require log—2B bits for expressing the elements.
Elements in a subset of a finite field, which is called algebraic torus, can be expressed with a small number of bits. There is known that when the order of an extension field to which the algebraic torus belongs is a product of powers of two prime numbers p and q, n=(p^m)×(q^w), at most, a compression rate (=the number of bits after compression/the number of bits before compression) is φ(n)/n. Herein, φ is Euler's function.
There is also known a method for realizing the compression rate of 1/4 and the compression rate of 1/6. According to the method, further compression is performed by obtaining data D1 in which the elements in an algebraic torus subset are compressed, and obtaining data D2, which is the partly deleted data D1, and an additional bit. Then, multivariable simultaneous equations obtained by a conditional equation of the algebraic torus subset and a relationship between the data D1 and the data D2 are solved so that candidates of the data D1 corresponding to the data D2 are obtained and the compressed data D1 is determined by using the additional bit.